/**
 * 堆排序
 * @param {*} nums
 * @returns
 */
 function sortArray(nums) {
  const N = nums.length;
  // 建堆 找到第一个非叶子节点，向上遍历
  for (let i = Math.floor(N / 2 - 1); i >= 0; i--) {
    // 对 i位置节点 调整堆
    heapify(nums, i, N);
  }
  // 排序过程 每一次循环都找出当前最大值（根节点），数组长度减一
  for (let i = N - 1; i > 0; i--) {
    // 根节点与最后一个节点交换位置（将此时最大元素移动到数组末尾）
    swap(nums, 0, i);
    // 对 此时的根节点 调整堆 最后的元素不用参与调整
    heapify(nums, 0, i);
  }
  return nums;
}

/**
 * 对节点i进行 调整堆
 * 满足：i节点以下的子堆是一个大顶堆
 * 调整范围 [i, length)
 * @param {*} nums
 * @param {*} i
 * @param {*} length
 */
function heapify(nums, i, length) {
  // 将i节点的值保存，这个过程就是给temp找到一个合适的位置
  let temp = nums[i]
  // j指向i的左孩子节点
  let j = 2 * i + 1;
  // 循环遍历[i, length)
  while (j < length) {
    if (j + 1 < length && nums[j] < nums[j + 1]) {
      // 父节点有右孩子 并且 左孩子小于右孩子 将j指向右孩子
      j++;
    }
    // 此时 j 指向 i 的孩子节点中较大的那个节点
    if (temp < nums[j]) {
      // 如果 父节点小于 j节点
      // 交换i，j的元素
      swap(nums, i, j);
      // 将i和j都下移一位
      i = j;
      j = 2 * i + 1; 
    } else {
      // 父节点 大于 孩子节点中最大的元素，就退出循环
      break;
    }
  }
}

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
